package com.modular.Shortest_path;

import java.util.*;

public class LC1786 {
    public static void main(String[] args) {
        int n = 5;
        int [][]edges = new int[][]{{1,2,3},{1,3,3},{2,3,1},{1,4,2},{5,2,2},{3,5,1},{5,4,10}};
        int []dist = new Solution1786().countRestrictedPaths1( n,edges);
        System.out.println("dist的长度："+dist.length);
/*        for (int i : dist) {
            System.out.println(i);
        }*/
        //System.out.println(i);

    }

}


class Solution1786 {

    //地杰斯特拉处理有向图的
    public int[] countRestrictedPaths(int n, int[][] edges) {
        Map<Integer, ArrayList<int[]>> graph = new HashMap<>();

        for (int[] edge : edges) {
            if (!graph.containsKey(edge[0]))
                graph.put(edge[0], new ArrayList<int[]>());
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});//edge[1]为目的节点
        }
        int []dist = new int[n+1];
        boolean []visit = new boolean[n+1];
        Arrays.fill(dist,Integer.MAX_VALUE);
        //dist[n] = 0;
        dist[1] = 0;
        // new一个小堆出来，按照dis升序排，一定要让它从小到大排，省去了松弛工作
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> dist[o1] - dist[o2]);
        queue.offer(1);

        while(!queue.isEmpty()){
            int nowindex = queue.poll();
            //说明该点已经访问过了
            if(visit[nowindex]) continue;
            //标记该点为已访问过
            visit[nowindex] = true;
            //获取当前点的相邻节点
            ArrayList<int[]> ints = graph.get(nowindex);
            if (ints == null) continue;//注意判断当前ints是否为空
            for (int[] anInt : ints) {
                int next = anInt[0];//相邻的节点
                // 如果这个邻居访问过了，继续
                if (visit[next]) continue;
                // 更新到这个邻居的最短距离，看看是不是当前poll出来的节点到它更近一点
                dist[next] = Math.min(dist[next], dist[nowindex] + anInt[1]);
                queue.offer(next);
            }
        }
        for (int i : dist) {
            System.out.println(i);
        }
        return dist;
    }

    //地杰斯特拉算法求解无向图的模板
    public int[] countRestrictedPaths1(int n, int[][] es) {
        // 预处理所有的边权。 a b w -> a : { b : w } + b : { a : w }
        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
        int mod = 1000000007;
        //边的处理，注意，这里是无向图！！！
        for (int[] e : es) {
            int a = e[0], b = e[1], w = e[2];
            Map<Integer, Integer> am = map.getOrDefault(a, new HashMap<Integer, Integer>());
            am.put(b, w);
            map.put(a, am);
            Map<Integer, Integer> bm = map.getOrDefault(b, new HashMap<Integer, Integer>());
            bm.put(a, w);
            map.put(b, bm);
        }

        // 堆优化 Dijkstra：求 每个点 到 第n个点 的最短路
        int[] dist = new int[n + 1];
        boolean[] st = new boolean[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[n] = 0;//
        Queue<int[]> q = new PriorityQueue<int[]>((a, b) -> a[1] - b[1]); // 点编号，点距离。根据点距离从小到大
       // PriorityQueue<Integer> q = new PriorityQueue<>((o1,o2)->dist[o1]-dist[02]);
        q.add(new int[]{n, 0});
        //q.offer(n);
        while (!q.isEmpty()) {
            int[] e = q.poll();
            int idx = e[0], cur = e[1];
            //int idx = q.poll();
            if (st[idx]) continue;
            st[idx] = true;
            Map<Integer, Integer> mm = map.get(idx);
            if (mm == null) continue;
            for (int i : mm.keySet()) {
                dist[i] = Math.min(dist[i], dist[idx] + mm.get(i));
                q.add(new int[]{i, dist[i]});
                //q.add(i);
            }
        }

        // dp 过程
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) arr[i] = new int[]{i + 1, dist[i + 1]}; // 点编号，点距离
        Arrays.sort(arr, (a, b)->a[1]-b[1]); // 根据点距离从小到大排序

        // 定义 f(i) 为从第 i 个点到结尾的受限路径数量
        // 从 f[n] 递推到 f[1]
        int[] f = new int[n + 1];
        f[n] = 1;
        for (int i = 0; i < n; i++) {
            int idx = arr[i][0], cur = arr[i][1];
            Map<Integer, Integer> mm = map.get(idx);
            if (mm == null) continue;
            for (int next : mm.keySet()) {
                if (cur > dist[next]) {
                    f[idx] += f[next];
                    f[idx] %= mod;
                }
            }
            // 第 1 个节点不一定是距离第 n 个节点最远的点，但我们只需要 f[1]，可以直接跳出循环
            if (idx == 1) break;
        }
        System.out.println(f[1]);

        return dist;
    }

    //地杰斯特拉处理有向图的模板
    public int[] networkDelayTime(int[][] times, int N, int K) {
        Map<Integer, List<int[]>> map = new HashMap<>();
        // 初始化邻接表
        for (int[] t : times) {
            map.computeIfAbsent(t[0], k -> new ArrayList<>()).add(new int[]{t[1], t[2]});
        }

        // 初始化dis数组和vis数组
        int[] dis = new int[N + 1];
        Arrays.fill(dis, 0x3f3f3f3f);
        boolean[] vis = new boolean[N + 1];

        // 起点的dis为0，但是别忘记0也要搞一下，因为它是不参与的，我计算结果的时候直接用了stream，所以这个0也就要初始化下了
        dis[K] = 0;
        dis[0] = 0;

        // new一个小堆出来，按照dis升序排，一定要让它从小到大排，省去了松弛工作
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> dis[o1] - dis[o2]);
        // 把起点放进去
        queue.offer(K);

        while (!queue.isEmpty()) {
            // 当队列不空，拿出一个源出来
            Integer poll = queue.poll();
            if (vis[poll]) continue;
            // 把它标记为访问过
            vis[poll] = true;
            // 遍历它的邻居们，当然可能没邻居，这里用getOrDefault处理就很方便
            List<int[]> list = map.getOrDefault(poll, Collections.emptyList());
            for (int[] arr : list) {
                int next = arr[0];
                // 如果这个邻居访问过了，继续
                if (vis[next]) continue;
                // 更新到这个邻居的最短距离，看看是不是当前poll出来的节点到它更近一点
                dis[next] = Math.min(dis[next], dis[poll] + arr[1]);
                queue.offer(next);
            }
        }
        return dis;//返回源点k到任何一个点的最短距离
    }
}